package com.jwetherell.my.problems.patternsearching;

/**
 * http://www.geeksforgeeks.org/searching-for-patterns-set-1-naive-pattern-searching/
 * 
 * Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function
 * search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[].
 * You may assume that n > m.
 * 
 * Examples:
 * 
 * 1) Input: txt[] = "THIS IS A TEST TEXT" pat[] = "TEST"
 * 
 * Output: Pattern found at index 10
 * 
 * 2) Input: txt[] = "AABAACAADAABAAABAA" pat[] = "AABA"
 * 
 * Output:
 * 
 * Pattern found at index 0
 * 
 * Pattern found at index 9
 * 
 * Pattern found at index 13
 * 
 * Pattern searching is an important problem in computer science. When we do
 * search for a string in notepad/word file or browser or database, pattern
 * searching algorithms are used to show the search results.
 * 
 * Naive Pattern Searching: Slide the pattern over text one by one and check for
 * a match. If a match is found, then slides by 1 again to check for subsequent
 * matches.
 * 
 * @author yatendra
 * 
 */
public class NaivePatternSearch {

	public static void main(String[] args) {
		// String textStr = "AABAACAADAABAAABAA";
		// String patternStr = "AABA";

		// String textStr = "AAAAAAAAAAAAAAAAAA";
		// String patternStr = "AAAAA";

		String textStr = "AAAAAAAAAAAAAAAAAB";
		String patternStr = "AAAAB";

		char[] text = textStr.toCharArray();
		char[] pattern = patternStr.toCharArray();

		NaivePatternSearch patternSearch = new NaivePatternSearch();
		patternSearch.printPatternIndices(text, pattern);
	}

	/**
	 * What is the best case?
	 * 
	 * The best case occurs when the first character of the pattern is not
	 * present in text at all.
	 * 
	 * txt[] = "AABCCAADDEE" pat[] = "FAA"
	 * 
	 * The number of comparisons in best case is O(n).
	 * 
	 * 
	 * What is the worst case ? The worst case of Naive Pattern Searching occurs
	 * in following scenarios.
	 * 
	 * 1) When all characters of the text and pattern are same.
	 * 
	 * txt[] = "AAAAAAAAAAAAAAAAAA" pat[] = "AAAAA".
	 * 
	 * 2) Worst case also occurs when only the last character is different.
	 * 
	 * txt[] = "AAAAAAAAAAAAAAAAAB" pat[] = "AAAAB"
	 * 
	 * Number of comparisons in worst case is O(m*(n-m+1)). Although strings
	 * which have repeated characters are not likely to appear in English text,
	 * they may well occur in other applications (for example, in binary texts).
	 * The KMP matching algorithm improves the worst case to O(n)
	 */
	private void printPatternIndices(char[] text, char[] pattern) {

		for (int i = 0; i < text.length - pattern.length + 1; i++) {

			int j;
			for (j = 0; j < pattern.length; j++) {
				if (text[i + j] != pattern[j])
					break;
			}

			if (j == pattern.length)
				System.out.println("Pattern found at index " + i);

		}
	}
}